package codeRandomThoughts.Test222完全二叉树中的节点个数;

import codeRandomThoughts.utils.TreeNode;

//二刷
//这个其实就是普通二叉树的节点个数加剪枝
public class Solution3 {
    public int countNodes(TreeNode root) {
        //终止条件
        if (root == null) {
            return 0;
        }

        //剪枝
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (left != null) {
            leftDepth++;
            left = left.left;
        }
        while (right != null) {
            rightDepth++;
            right = right.right;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }

        //单层递归逻辑,记得加上根节点自身!!!
        return countNodes(root.left) + countNodes(root.right)+1;
    }
}
